package leetcode_5000;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class _按字典序排列最小的等效字符串 {
	
	public static void main(String[] args) {
		_按字典序排列最小的等效字符串 test = new _按字典序排列最小的等效字符串();
		System.out.println(test.smallestEquivalentString("dfeffdfafbbebbebacbbdfcfdbcacdcbeeffdfebbdebbdafff","adcdfabadbeeafeabbadcefcaabdecabfecffbabbfcdfcaaae", "abcdfegg"));
		System.out.println(test.smallestEquivalentString("leetcode", "programs", "sourcecode"));
		System.out.println(test.smallestEquivalentString("hello", "world", "hold"));

		System.out.println(test.smallestEquivalentString("parker", "morris", "parser"));

	}
	
	 public String smallestEquivalentString(String A, String B, String S) {
	        Map<Integer,Set<Character>> map = new HashMap<Integer,Set<Character>>();//表示一个组
	        char[] charA = A.toCharArray();
	        char[] charB = B.toCharArray();
	        int[] hash = new int[26];//char - int - set
	        for(int i=0;i<charA.length;++i) {
	        	if(charA[i] == charB[i]) continue;
	        	if(hash[charA[i]-'a'] ==0 && hash[charB[i]-'a'] == 0) {//init
	        		int index = map.size()+1;
	        		Set<Character> set = new HashSet<Character>();
	        		set.add(charA[i]);
	        		set.add(charB[i]);
	        		map.put(index,set);
	        		hash[charA[i]-'a'] = index;
	        		hash[charB[i]-'a'] = index;
	        	}else {
	        		if(hash[charA[i]-'a'] ==0) {//A没有初始化
	        		   Set<Character> set = map.get(hash[charB[i]-'a']);
	        		   set.add(charA[i]);
	        		   hash[charA[i]-'a'] = hash[charB[i]-'a'];
	        		}else if(hash[charB[i]-'a'] ==0) {//B没有初始化
	        			Set<Character> set = map.get(hash[charA[i]-'a']);
	        			set.add(charB[i]);
	        			hash[charB[i]-'a'] = hash[charA[i]-'a'];
	        		}else {
	        			Set<Character> setA = map.get(hash[charA[i]-'a']);
	        			Set<Character> setB = map.get(hash[charA[i]-'a']);
	        			char minA =help(setA);
	        			char minB =help(setB);
	        			if(minA<minB) {
	        				 int indexA = hash[charA[i]-'a'];
	        				 for(Character now:setB) {
	        					 setA.add(now);
	        					 hash[now-'a'] = indexA;
	        				 }
	        			}else if(minA > minB){
	        				int indexB = hash[charB[i]-'a'];
	        				 for(Character now:setA) {
	        					 setB.add(now);
	        					 hash[now-'a'] = indexB;
	        				 }
	        			}
	        		}
	        	}
	        }
	        char[] m = new char[26];
	        Map<Integer,Character> cache = new HashMap<>();
	        for(int i=0;i<26;++i) {//a-z 映射的最佳值  hash[i]表示组
	        	if(hash[i] == 0) {
	        		m[i] = (char) (i+'a');
	        	}
	        	else if(cache.containsKey(hash[i])) {
	        		m[i] = cache.get(hash[i]);
	        	}else {
	        		char res = help(map.get(hash[i]));
	        		m[i] = res;
	        		cache.put(hash[i], res);
	        	}
	        }
	        StringBuilder sb = new StringBuilder();
	        char[] charS = S.toCharArray();
	        for(char c:charS) {
	        	sb.append(m[c-'a']);
	        }
	        return sb.toString();
	 }
	 
	 private char help(Set<Character> set) {
		 char res = '{';
		 for(char c:set) {
			 if(c < res) res = c;
		 }
		 return res;
	 }
}
